#define _CRT_SECURE_NO_WARNINGS 1
//反转链表
//struct ListNode* reverseList(struct ListNode* head) {
//    struct ListNode* n1, * n2, * n3;
//    n1 = NULL;
//    n2 = head;
//    if (head)//防止头结点为空
//        n3 = head->next;//n3储存下一个结点
//    while (n2)//当n2为空时结束，此时头指针为n1
//    {
//        n2->next = n1;
//        n1 = n2;
//        n2 = n3;
//        if (n3)
//            n3 = n3->next;
//    }
//    return n1;
//}

//删除val
//struct ListNode* removeElements(struct ListNode* head, int val) {
//    struct ListNode* cur = head;
//    struct ListNode* prev = head;
//    while (cur)
//    {
//        if (cur->val == val)
//        {
//            if (cur == head)
//            {
//                head = cur->next;
//                free(cur);
//                cur = head;
//            }
//            else
//            {
//                prev->next = cur->next;
//                free(cur);
//                cur = prev->next;
//            }
//        }
//        else
//        {
//            prev = cur;
//            cur = cur->next;
//        }
//    }
//    return head;
//}
//2.

//返回中间结点
// 1，两次遍历法
//struct ListNode* middleNode(struct ListNode* head) {
//    int i = 0;
//    struct ListNode* cur = head;
//    struct ListNode* tmp = head;
//    while (cur)
//    {
//        i++;
//        cur = cur->next;
//
//    }
//    i /= 2;
//    while (i > 0)
//    {
//        tmp = tmp->next;
//        i--;
//    }
//    return tmp;
//
//}
//2,快慢指针法
//struct ListNode* middleNode(struct ListNode* head) {
//struct ListNode* fast = head, * slow = head;
//while (fast && fast->next)//奇数偶数不同情况的结束条件
//{
//    slow = slow->next;
//    fast = fast->next->next;
//}
//return slow;
//}


//.输入一个链表，输出该链表中倒数第k个结点
// 1,两次遍历
//int kthToLast(struct ListNode* head, int k) {
//    struct ListNode* cur = head, * tmp = head;
//    int i = 0;
//    while (cur)
//    {
//        cur = cur->next;
//        i++;
//    }
//    i = i - k;
//    while (i--)
//    {
//        tmp = tmp->next;
//    }
//    return tmp->val;
//}

//2.快慢指针(距离上)
//int kthToLast(struct ListNode* head, int k) {
//    struct ListNode* fast = head, * slow = head;
//    while (fast)//当fast=NULL时，slow就是第倒数k个结点，因为fast先走了k个结点
//    {
//        if (k > 0)
//        {
//            fast = fast->next;
//            k--;
//        }
//        else
//        {
//            slow = slow->next;
//            fast = fast->next;
//        }
//    }
//    return slow->val;
//}

//合并两个有序链表
//struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2) 
//{
//if (list1)
//return list2;
//if（list2）
//return = list1;
//struct ListNode* head = NULL, * tail = NULL;
//while (list1 && list2)
//{
//    if (list1->data < list2->data)
//    {
//        if (tail == NULL)
//        {
//            head = tail = list1;
//        }
//        else
//        {
//            tail->next = list1;
//            tail = tail->next;
//        }
//        list1 = list1->next;
//    }
//    else
//    {
//        if (tail == NULL)
//        {
//            head = tail = list2;
//        }
//        else {
//            tail->next = list2;
//            tail = tail->next;
//        }
//        list2 = list2->next;
//    }
//}
//if (list1)
//tail->next = list1;
//if（list2）
//tail->next = list2;
//return head;
//}